
// 1. 纵向扫描
// 时间复杂度：O(mn) m 表示字符串数组中所有字符串的平均长度，n 表示字符串数组的大小
// 空间复杂度：O(1)
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) {
        char* res = (char*)malloc(sizeof(char));
        res[0] = '\0';
        return res;
    }

    int rows = strsSize;
    int cols = strlen(strs[0]);
    for (int i = 0; i < cols; i++) {
        char firstChar = strs[0][i];
        for (int j = 1; j < rows; j++) {
            if (strlen(strs[j]) == i || strs[j][i] != firstChar) {
                char* res = (char*)malloc(sizeof(char) * (i + 1));
                strncpy(res, strs[0], i);
                res[i] = '\0';
                return res;
            }
        }
    }

    return strs[0];
}

char* longestCommonPrefix_help(char* str1, char* str2) {
    int len = fmin(strlen(str1), strlen(str2));
    int index = 0;
    while (index < len && str1[index] == str2[index]) index++;

    char* res = (char*)malloc(sizeof(char) * (index + 1));
    strncpy(res, str1, index);
    res[index] = '\0';
    return res;
}

// 2. 横向扫描
// 时间复杂度：O(mn) m 表示字符串数组中所有字符串的平均长度，n 表示字符串数组的大小
// 空间复杂度：O(1)
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) {
        char* res = (char*)malloc(sizeof(char));
        res[0] = '\0';
        return res;
    }

    char* prefix = strs[0];
    for (int i = 1; i < strsSize; i++) {
        prefix = longestCommonPrefix_help(prefix, strs[i]);
        if (strlen(prefix) == 0) {
            char* res = (char*)malloc(sizeof(char));
            res[0] = '\0';
            return res;
        }
    }

    return prefix;
}

char* lcp(char** strs, int left, int right) {
    if (left == right) {
        int n = strlen(strs[left]);
        char* res = (char*)malloc(sizeof(char) * (n + 1));
        strncpy(res, strs[left], n);
        res[n] = '\0';
        return res;
    }

    int mid = left + (right - left) / 2;
    char* leftLcp = lcp(strs, left, mid);
    char* rightLcp = lcp(strs, mid + 1, right);

    return longestCommonPrefix_help(leftLcp, rightLcp);
}

// 3. 分治思想
// 时间复杂度：O(mn) m 表示字符串数组中所有字符串的平均长度，n 表示字符串数组的大小
// 空间复杂度：O(mlogn) 空间复杂度主要取决于递归调用的层数，层数最大为 logn，每层需要 m 的空间存储返回结果。
char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) {
        char* res = (char*)malloc(sizeof(char));
        res[0] = '\0';
        return res;
    }
    return lcp(strs, 0, strsSize - 1);
}